package questions;

import lombok.val;

import java.util.HashMap;
import java.util.Map;

public class LRUDemo {

    public static void main(String[] args) {
        LRUCache lruCache = new LRUCache(3);
        lruCache.put(1,1);
        lruCache.put(2,1);
        lruCache.put(3,1);
        lruCache.get(1);
        lruCache.put(4,1);
        System.out.println(lruCache);
    }
}

class LRUCache {
    private DoubleLinkedList<Integer, Integer> doubleLinkedList = new DoubleLinkedList<>();
    private Map<Integer, Node<Integer, Integer>> valMap = new HashMap<>();
    private Integer capacity;

    public LRUCache(int capacity) {
        this.capacity = capacity;
    }

    public int get(int key) {
        if (valMap.containsKey(key)){
            Node<Integer,Integer> node = valMap.get(key);
            doubleLinkedList.move2First(node);
            return node.val;
        }
        return -1;
    }

    public void put(int key, int value) {
        if (valMap.containsKey(key)){
            Node<Integer,Integer> node = valMap.get(key);
            node.val=value;
            doubleLinkedList.move2First(node);
        }else {
            //new node
            Node<Integer,Integer> newNode= new Node<>(key,value);
            if(capacity <= valMap.size()){
                Node<Integer,Integer> old=doubleLinkedList.getLast();
                doubleLinkedList.removeNode(old);
                valMap.remove(old.key);
            }
            doubleLinkedList.addNode(newNode);
            valMap.put(key,newNode);
        }
    }

    class DoubleLinkedList<K, V> {
        Node<K, V> head;
        Node<K, V> tail;

        public DoubleLinkedList() {
            this.head = new Node<>();
            this.tail = new Node<>();
            this.head.next = tail;
            this.tail.prev = head;
        }

        public void addNode(Node<K, V> node) {
            head.next.prev=node;
            node.next=head.next;
            head.next=node;
            node.prev=head;
        }

        public Node<K, V> getLast() {
            return tail.prev;
        }

        public Node<K, V> getFirst() {
            return head.next;
        }

        private void move2First(Node<K, V> node){
            removeNode(node);
            addNode(node);
        }

        public void removeNode(Node<K, V> node) {
            node.prev.next = node.next;
            node.next.prev = node.prev;
            node.next = null;
            node.prev = null;
        }

    }

    class Node<K, V> {
        Node<K, V> prev;
        Node<K, V> next;
        private K key;
        private V val;

        public Node() {
            prev = next = null;
        }

        public Node(K key, V value) {
            this.key = key;
            this.val = value;
            prev = next = null;
        }
    }
}